969 847436
389407661 277797909 412491247 630867460 737533052 224637636 262678765 526036729 827226290 746112259 405839853 90829955 785485469 260949534 103441407 354237312 862784048 542344612 454670358 341033809 288295809 384144871 337499532 381509211 39062345 959385215 789611164 811481222 97362279 928848071 900667623 35932097 342863709 858549855 536243184 768368252 859595473 946105768 10738592 720983084 234952206 488816715 748355266 472677834 434227840 511297458 62897544 252532820 342125884 176240526 967400964 569815371 834677109 487536719 49832624 134516020 297142536 291614639 546223847 214559767 995356401 620341032 472639849 734479363 147029972 30093945 445085403 134610312 477697653 49157669 521218117 572078139 941344320 738955251 831721874 324052278 929549762 264898415 173308435 498188693 16423725 746930280 232359677 337163514 675284696 126008688 336167910 127451145 629377469 806976607 757335372 765699309 258304506 560927952 664350478 992498129 952895312 675387043 563721457 404279144 6533031 571241593 920275228 305103206 239766408 200044091 383847068 288110341 487506081 114911124 392056289 48039809 595446341 310208114 25073471 809960604 979377130 888191369 448282990 40906011 998236585 344261328 33702411 469122374 701822657 808286209 697528853 908295020 198221843 284652829 392225904 462912605 252232359 933053670 750318693 393847278 557264423 237319012 535567392 885220729 608835423 591460449 815110961 245574234 857709763 291277293 612494092 734229619 697806057 89926874 453862281 157010601 161065226 643425600 374253924 254319972 368986502 982776571 452107966 902219539 920894557 645158440 703095194 786818726 880318390 44748204 548847713 816231954 888219228 66248109 338959966 418112209 910351931 740357654 230948419 242550367 389708520 138241304 686579875 201769662 15154711 574833572 330709109 945655539 986379810 644818929 727951255 774386566 241352841 211792892 100730185 624414982 389832812 899499011 181234350 281879683 688109331 420298505 774092111 7937554 452438631 288732502 207945111 236492109 420629366 345094900 496993623 977410000 753287922 315132467 520542276 55546813 296294835 674539045 88071284 559985209 482108209 766434083 148595429 394500077 827351562 718273350 521207286 204851077 710294658 215792366 407999980 62990900 898829566 966145343 167831407 388507183 703681672 801714847 681857034 212547373 610843982 679409466 57387694 342598382 811797283 734863742 323037231 689468337 293265917 691063967 626757062 532580028 135985781 914191124 51175821 102342359 593402954 160052504 445645574 896852689 383992030 151474986 179993493 708955642 163146679 51255949 465901825 549068967 211921664 203218889 151356919 345719474 456362501 965499688 560171143 703203831 516016571 186423610 734568101 745728216 901418805 55618897 649846441 156470458 778989616 394311686 43090383 89526406 88017288 973113266 374855864 771223849 7785920 287345398 862499304 241375252 543251839 382250804 411821126 224656828 592923662 10988307 922108830 497021467 256970715 31073022 40300834 793411373 30858488 825067430 756548581 463845749 741096348 680827004 418253151 556120693 265890977 852806712 764403692 911795001 106564612 726002005 166163789 570390733 60985193 777254546 4751653 304228546 824427157 336797554 901461884 706103726 790028786 253533373 784924480 20926376 709005582 307788541 466036928 241167568 527320348 366922498 167871535 662434245 295222641 715480670 551475751 403192877 258855432 352656874 293938723 717622065 676175359 784273983 432313091 382943741 33689112 641992766 242637196 72853061 364446009 584440713 371477734 686720187 719308524 943954183 859787036 437925786 210077152 627503972 812886943 573707038 932259430 940424078 238838724 983685641 574449396 586733881 952484673 97490976 782353062 464549724 30205108 756718252 350671288 767337138 610137628 111815930 7990797 813398587 933543774 704390875 210208171 409451448 850585793 851044133 139777341 185606706 326283122 846766128 711548559 371967603 454224385 518046297 191281430 701529995 692475106 680206978 919994982 479473485 824493805 693339280 637363385 188291791 197525983 653821420 219566959 350590190 114205399 133762051 346747272 814210247 804765913 145847494 321941548 962262079 56038223 865237291 560375587 361502845 782246018 688004522 897615710 993679978 365393957 666353856 974213996 503781176 134035403 579600751 935138309 632808664 854663532 514692540 496512131 763641474 981263332 42844464 734189412 950956337 906553204 213753688 110864074 526789156 688388671 754750021 144204539 322612575 365957838 740776717 689572577 443946536 694283405 39640648 128784522 744976266 260033100 210610323 756619689 664765653 326867646 656168208 816234003 770621468 137481469 271927781 431867971 496204981 259003140 129607864 61354968 433505213 393020980 388629306 191269394 897072274 718957520 706797465 225977432 659987799 15844736 75516683 631291572 505127283 506642386 531921994 230467157 298923026 638408884 88840211 236327436 664798882 841571836 655333286 179652304 732806488 486501344 332279113 156809786 748757417 826777982 622461125 18561801 648749777 849268566 961323495 492102560 349582415 998453194 212478720 596732547 372079207 385461157 641551206 630986462 76464287 42029201 487207409 981204734 959262274 28293535 199746431 139560149 179735264 842851267 170927472 774239866 190244556 743688278 5954602 193466023 692710812 974483858 408607126 633762105 112154797 763326746 625257377 539030964 246121373 175407215 909659836 230757309 425710287 731045755 747399261 816312221 863170026 109411594 695573372 881681605 90894938 244802892 633295127 477178948 794711502 813099093 538354862 961459027 56390328 32411806 647246023 903080394 763727568 351745409 119847275 819613352 692683154 384243648 42477223 789587086 795198651 258113534 664111372 203572292 985197776 650561348 179580464 672335156 600138134 970228606 99423019 432333802 794117275 39831036 156216603 506579098 5325740 384438770 443065760 228397466 297762141 284317944 465190240 210247139 188130181 309236618 155706500 254443924 892783038 621431688 798719802 413823087 545988585 913839800 332378161 601583706 827705000 73218879 835666720 117840864 760481763 132087340 332870975 583295150 306484548 862951405 517018059 127133206 377597626 902023384 994209927 58390927 74663162 313959332 809686070 977952050 43512313 378581485 842125602 605768767 535427955 352573619 171964312 748365718 753013608 543867611 818729066 818587711 337366681 868443053 911117163 571098082 341512463 544106324 223470582 676368208 440826005 770554721 161061736 147598584 854658873 360630089 530436001 408768882 976799695 655697634 821868424 725782520 975561838 235241706 384677252 640832232 985358065 692364672 196570627 317811268 99678583 915328681 811800566 104178225 799518947 594655948 530823507 124076411 343701340 755488566 214994322 940159504 642433230 795379352 502438961 226305921 620239720 769395588 816793393 211194756 614737948 747406579 111595926 245708916 38132515 941308609 233353706 395896783 740604022 357658159 997664954 598810807 208797270 352849505 865647384 571309170 536148420 899753694 407768855 186094314 311398665 476628499 439513683 11440942 292395056 617921488 616453734 563695087 791324039 52259273 434441076 9698820 79693346 337726998 636514976 335357670 975900760 389252531 875495572 271722805 523567172 358323457 494920702 920341809 749965893 210100291 303317517 110465857 459825534 584439330 613772024 186212976 562016855 666888746 940728439 256441067 399909626 139935563 397904968 7309956 31857623 37897304 960361131 476081458 460559392 595341963 599199463 309238671 914075213 576347135 15572419 367663448 707737242 858935349 896344077 904206321 80250756 935797392 152059671 245090527 942806096 317248729 197476149 941498955 686079876 286120379 830399552 46947206 244888428 990150984 819403798 874495359 299630230 465607026 215474967 182626127 963540566 440916627 747711657 550642862 215037763 845955045 852604854 750988410 124349368 975073291 943168809 974819127 468166228 701020551 641970805 167764362 568022138 387853121 991244301 326279357 607081170 687951110 342353389 195188543 260681670 408690183 502733840 922711841 935439366 879724886 212654327 102439577 923599621 645829228 612011049 618829443 174078329 727785894 719718573 338736859 893141983 859181763 512714641 344451396 32342260 604414312 340654695 324766596 881579069 957792668 68860867 733795333 831754880 979934796 97987518 641509974 986712649 262885832 8800886 311431592 14969958 905489988 309321355 863026514 164830827 119809112 93457316 870832462 681990959 369595265 217848552 404768953 128978765 216965278 249246598 512474711 121270692 125661299 397572397 496558348 919575512 308197417 131817620 956071524 388810447 222794700 730627571 494252812 756270900 301094092 962776456 403128150 752507383 483618429 361554964 440674745 962199242 929833622 732851547 413766991 983186086 242762678 109590184 652032086 624369732 972639194 370803526 987269808 87166629 654270697 158675208 444100194 30509451 40812840 537367746 635025432 200327165 950860230 631894733 861146528 809433799 577958226 879755143 95454827 93557495 691799615 896272849 79279631 230463585 851101031 989908879 646801607 690493468 798161541 92546092 469834225 973690116 77279417 575442707 104538767 355684406 914431752 939818551 137572807 601549206 345302746 404907660 63390051 420010060 185415802 14747787 305280082 709993282 729929114 480311474 790672165 608459176 288413644 755237378 670179987 392524657 883358474 69601919 151706101 172991955 371188270 793212340 781051850 376824779 172566907 123453740 682936372 14771863 222935826 18321658 933883258 681488442 65594750 329481778 300185732
524680187 341102121 686076781 806654818 883505894 450236900 664394057 84552134 18726985 518964579 191922407 190120837 67285561 355658175 413134956 972376345 39623691 769848562 366481280 485297698 218641627 653434462 818031058 834850784 633720840 933611847 939076497 705350587 427112885 802377044 657489396 846000572 292173130 708076306 198617012 216649489 420184050 97036401 789224845 870485645 972552987 470271813 961735873 856918309 738548984 701501382 38906772 634655860 597820162 277696272 108082129 484491576 152540275 803635108 778344771 860649938 447981258 72175077 867352125 575514314 100956746 999025820 219771411 610225481 103443578 164368245 813955999 986364318 287233702 655884672 671813053 877137338 890217564 92036528 332408270 966943667 162973169 586189151 428487225 309256260 782445818 42468552 69146854 922058060 844731603 142812044 388580801 543955531 963078427 263030574 460737341 450353896 117260854 464711575 288249038 294379885 80751050 222987154 715318638 435191625 167009602 393075537 856310297 654442381 814019150 861063398 350184528 536168816 212813153 505109707 92638362 398299851 989225522 879573595 605385983 193434270 281957435 820883030 122845067 231783817 333472061 741048673 719995089 932460116 525109690 749268612 144204389 810082407 12837754 499018666 793717601 609321042 99000327 380938276 878353121 79628871 465186608 506353447 404883079 882465947 395962250 106021449 386494711 822995017 668050666 74691080 204662364 859555182 872495852 936490563 728299746 524821966 267466096 178333375 931801402 687448398 479517975 937167779 533856537 373434488 249980362 571724284 692300728 270405882 872654132 182804538 155491413 323632679 916952387 815537329 715739825 351006068 881575083 639103513 577534353 339312380 902109538 239093263 951813950 568489469 157921061 451411858 219392516 487730009 336158706 429650310 495498934 958608918 414537356 37449012 186934056 596391390 849707259 316071112 252345012 808295296 955912457 42669522 663102646 128429933 503228101 943877574 692497168 752840764 551297796 781807740 48230055 781358374 871032283 265001136 721991139 663413386 573952294 297507459 813339955 872999530 222140165 274842104 710067591 593163501 709275226 357084536 98407124 916783323 744223052 826589774 922480276 286052900 101043654 546058028 343958595 891562585 75587064 654868133 984956387 904406321 484664533 595378096 890690169 472567558 384832148 67313707 494230158 218725717 417398064 27796310 821309102 502705986 90201320 794861140 770203116 16689169 815812287 166296750 170576989 670104494 173561597 931785935 588522392 146593574 389780908 223650952 573525308 919370028 751652636 36289422 50162026 410780821 520428127 35153399 299723079 257574620 657080781 228933825 755404668 118958239 911629186 472668748 231074998 917495840 334081499 984023770 554794022 309083077 174999549 911634198 914530305 953700504 107307598 883902090 954077185 498442439 568289530 221808167 386648034 1414181 379063407 889044673 900961766 291666599 676566497 905580433 85518674 304777449 999136711 181182641 34338543 824024231 385024604 260800419 937471369 881855812 43580447 380340171 437105779 385081414 475424339 182281968 734883842 824199639 996817792 494896063 500534797 811827526 992269808 523243080 65480820 729101188 196495923 43693695 123926422 758622120 401583003 636864188 58293977 947795819 253164225 136561212 855021861 193831853 369583102 370811293 609471337 909583086 111663602 543088486 387806997 359166421 733126145 541692029 968382623 881796013 53224657 577930926 951139326 249627875 988150478 650684203 582191922 419300746 748365478 964422407 258514618 45014487 965893070 3759546 830803996 152396964 831037178 391794592 290305632 242988529 430174888 871831674 277363861 378571103 669941655 227890155 821304907 506433203 561106760 234190332 84291608 637005913 253954692 870345624 767578132 463501278 601134037 812234513 542731868 233516661 176453643 581083289 987949458 590304116 45749432 433410250 867349851 343778516 277519029 741455135 856371936 655383987 538538651 515831416 433043278 930637525 331343179 75785626 187783766 727531807 443978343 553202093 169210541 220593180 221210838 806263484 458283149 974540408 137765700 991884856 363191347 556760711 204518047 972111734 285174367 389135551 51363995 299012140 201936599 323342393 695131183 696653560 530720995 134854452 551213590 886745049 187538386 707433362 211628879 56163508 894855541 79886682 556737950 405647312 151566495 149846836 512913928 267225178 965060011 175495920 804018523 24077026 109015285 760884735 599244964 237236700 393115487 815264760 55508406 256271904 777110734 700975381 370597802 397599595 956671659 238833843 75561305 733984988 407453283 69339094 196165092 481548663 140338663 266739618 71047981 561168038 976398381 788728291 71537755 365341362 961732525 69664646 7122010 797808974 741269732 28783902 165403225 575399437 680808148 215909216 221670986 768772839 61195650 571082663 876127077 842837177 416159351 768800881 271284901 247208897 396153664 777146847 121725257 427317797 152976879 259366457 582639957 352091245 589109143 539277416 910052878 230076933 580040915 984170619 474508930 423082429 586460736 453366306 221859838 617237576 998460670 490415926 77332629 353436352 418761523 591155247 685311904 721970976 79425672 114918060 736032825 247621321 190494890 175248879 648261054 758537982 274996170 545379678 377812052 587018599 72592670 581664003 200404322 11055762 599213406 549593613 189880338 244594797 307415879 616496973 556063699 47749326 288321563 775608762 606486233 971207659 717316639 126614765 178895004 429768418 218556700 666060710 248172117 459728435 573126879 238639685 109585284 836230720 653559226 176073553 726152812 945277908 193807104 80656885 610261141 428623513 486413708 856454270 702565706 702675360 742498363 356848862 470413849 504611293 705647213 723463980 634998102 632874665 721878152 780116514 616508055 298407487 195343989 643468190 292034873 841838655 162239521 741041441 236906202 119969325 778576894 875527763 71723485 751313906 555964799 850360189 825660393 483191386 515516319 176026637 933426794 951974805 617672539 354872086 922637583 135452599 663735347 741128141 580845642 258564921 92146861 46494733 627817427 737220981 261744850 722274516 170086693 727656237 275630767 581810372 913994240 252576004 517950678 791478947 631293157 529426947 847125722 260577243 642497437 414358038 424602070 806792955 579733939 553076365 824403175 56413236 830974709 215381148 915109805 555142108 220924407 610164187 672523983 456101102 657593487 989488838 656816244 824489353 568843354 427648317 544996554 960087405 120368438 608492294 16628866 690902657 900070342 362073158 474755410 812674895 781124594 116792332 537746034 224903558 915044708 115286214 432713504 961210999 789427211 390595786 486593820 775046041 986031260 939311823 769190188 235775238 598180620 127577201 982046617 900815867 365527831 279641264 384109232 849941340 441203901 163342961 311239491 975107117 265001151 130053884 751053606 449987610 890475814 593773692 728024498 240662000 564362685 853564546 659054148 266611234 639291026 994920067 920782015 387694405 371832953 661003349 510031366 671835284 344526729 299630262 43992707 628115564 759820700 575900101 229193379 740353233 905964243 52850567 743765848 654775784 905503248 321551459 957159573 807969403 583204731 161573286 305206742 539468408 95527166 27345921 573849749 457055090 243151561 388930566 499414 787278623 589687758 461359278 830650268 850882520 301011014 954286550 223586161 641074460 959393834 852339900 441270498 825936397 273250746 666570375 26915073 331922417 946990586 381391549 432964578 166365874 321698608 630621643 512344350 272470879 767258472 410992001 524622419 907123881 121805552 296072595 200887713 72584550 992677084 904950297 31349806 478046482 147087747 382957071 969576100 330590281 146854656 72914902 782756270 326311246 209591218 76643761 672856702 862777992 266091196 680366153 177024842 843084031 775916165 248061226 940132810 228113635 221470010 38123332 568153020 71505926 273445703 712141162 258095969 18269277 656518114 864646870 286801917 187254914 218471808 319343011 128052826 64894517 196912222 882678610 378551109 926603478 824067321 163165510 488238608 365971949 244650646 764460872 366021391 597099939 784716731 854813187 21994523 342954310 236451508 592237961 14727954 82016201 830164495 431809996 692163156 87695425 533841696 897241894 172285768 905111657 753644158 966207186 219869909 233198879 60918404 115759984 27831273 26909925 452101073 165566853 552189942 195449441 85050312 834278392 824511856 571592925 454882065 707006614 728344656 192280263 678884374 640942736 743696020 238555698 232977287 596867832 651094204 587089748 152596694 409078087 985955919 876743430 349465276 400846810 780712020 226076999 835353522 745924720 290781658 243667897 500112505 835096238 977684592 592814115 993858195 304296091 704677549 857140461 487321799 459201316 58661545 537077159 237442977 891891865 834193538 736292226 122422255 528258862 782049497 525621717 584433477 286855035 812294482 792568985 407131770 181255421 238995735 869594350 546776105 308073107 969711958 123413396 269089073 505340673 709055934 606018419 397112118 562193776 910886150 885587987 979621661 31006188 358825831 858947108 859303316 796413413 524862749 410916856 583492487 340596399 731632873 173602308 662246572 22586370 25754770 376348003 708913145 611509370 920299871 856425555 628867624 768967191 466655903 138568885 904684602 123583167 442760225 546774161 514454001 243688119 354310332 221933712 113493588 973253934 878580936 17037440 324344367 440571571 389322403 370308564 777419920
